The present invention relates to an encoder and a decoder for residue number system data conversion in a digital signal processing circuit.
Digital signal processing circuits such as a digital filter and the like for performing a residue number system operations have been proposed. Refer to "IRE Transactions On Electronic Computers," Vol. EL-8, No. 6, June 1959, pp. 140-147. "IEEE computer," Vol. 17, No. 5, May 1984, pp. 50-61" and "The Transactions of the Institute of Electronics and Communication Engineers, '84/4 Vol. J67-1, No. 4 pp. 536-543."
Since a carry operation is unnecessary in a residue number system, operations on digital signals can be performed in the residue number system with high accuracy and high speed.
After input binary data is converted into a set of residue data (hereinafter it is called as RNS data), and after a desired operation is carried out in a residue number system, the obtained RNS data are converted back into output binary data.
If a conversion table is constituted using ROM (Read Only Memory) for the encoder and the decoder, the RNS data and the binary data can be obtained with high speed.
However, to convert n-bit binary data using a ROM table into RNS data represented, for example, by a plurality of K.sub.i -bit residue data, a ROM table capacity A represented by the following expression is needed with respect to each of modula M.sub.i (where i=0, 1, 2, . . .) EQU A=2.sup.n .multidot.K.sub.i (bit)
For example, when the binary data and the residue data are represented by 14 bits and 4 bits, respectively, the ROM table capacity represented by the following expression is needed. EQU A=2.sup.14 .times.4=65536 (bit)
A problem with using a ROM table of such a large capacity is that the access time of the ROM table becomes too large to convert binary data into RNS data within acceptable time constraints.
As for a method by which RNS data are demodulated back into binary data, a Mixed Radix Conversion Method (hereinafter called as MRC method) is known as shown in the paper entitled "Residue Arithmetic and its Application To Computer Technology (1967)".
In this method, residue data composing RNS data are applied with scale-down processing in order step by step using a multiplicative inverse element of a value of one modulus for that of another modulus to reduce the number of the residue data. After the residue data remaining finally have been applied with multiplication processing using a fixed modulus, the RNS data then are converted to binary data by obtaining additional data.
In this case, however, since the residue data are applied with scale-down processing in order step by step, there is a problem that the whole configuration becomes large-scaled.
Another problem with using a residue number system is that although a negative number can be represented by 2's complement binary against natural or straight binary in binary data, a negative number is not particularly defined in RNS data. Therefore operations for processing negative numbers become complicated.